package com.tgy.leetcode;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.Objects;

class MyHashSet {

    private static class Node{

        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    private static final float FACTOR = 0.75f;

    private int len;
    private int size;

    private Node[] nodes;


    /** Initialize your data structure here. */
    public MyHashSet() {

        len = 10;
        nodes = new Node[len];
    }

    public void add(int key) {

        if (contains(key)) {

            return;
        }

        expand();

        int index = key % len;

        Node node = nodes[index];
        Node newNode = new Node(key);

        newNode.next = node;
        nodes[index] = newNode;
        size++;
    }

    public void remove(int key) {

        if (!contains(key)) {
            return;
        }



        int index = key % len;
        Node node = nodes[index];
        Node preNode = null;
        while (node != null) {

            if (node.val == key) {

                break;
            }

            preNode = node;
            node = node.next;
        }

        if (preNode != null) {

            preNode.next = node.next;
        }else {

            nodes[index] = node.next;
        }
        size--;
    }

    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {

        int index = key % len;

        Node node = nodes[index];
        while (node != null) {

            if (node.val == key) {
                return true;
            }
            node = node.next;
        }

        return false;
    }

    private void expand() {

        if (size < len * FACTOR) {

            return;
        }

        int newLen = len + (len >> 1);
        Node[] newNodes = new Node[newLen];
        for (int i = 0; i < nodes.length; i++) {

            Node node = nodes[i];
            while (node != null) {

                int key = node.val;
                Node newNode = new Node(key);
                int index = key % newLen;
                newNode.next = newNodes[index];
                newNodes[index] = newNode;

                node = node.next;
            }
        }

        nodes = newNodes;
        len = newLen;

    }

}

public class _705_设计哈希集合 {

    public static void main(String[] args) {

        MyHashSet myHashSet = new MyHashSet();
        myHashSet.add(1);      // set = [1]
        myHashSet.add(2);      // set = [1, 2]
        System.out.println(myHashSet.contains(1));
        System.out.println(myHashSet.contains(3));
        myHashSet.add(2);      // set = [1, 2]
        System.out.println(myHashSet.contains(2));
        myHashSet.remove(2);   // set = [1]
        System.out.println(myHashSet.contains(2));

        for (int i = 0; i < 100; i++) {

            myHashSet.add(i);
        }

        System.out.println(myHashSet.contains(90));
        myHashSet.remove(87);
        System.out.println(myHashSet.contains(87));
    }

}
